home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
ftp.cs.arizona.edu
/
ftp.cs.arizona.edu.tar
/
ftp.cs.arizona.edu
/
icon
/
newsgrp
/
group94b.txt
/
000010_icon-group-sender _Fri Aug 19 10:05:22 1994.msg
< prev
next >
Wrap
Internet Message Format
|
1995-02-09
|
4KB
Received: by cheltenham.cs.arizona.edu; Fri, 19 Aug 1994 10:35:12 MST
Date: Fri, 19 Aug 1994 10:05:22 +0700
From: swampler@noao.edu
Message-Id: <9408191705.AA24746@orpheus.gemini.edu>
Subject: Re: Backtracking and reversible assigment
To: icon-group@cs.arizona.edu
Content-Length: 3786
Errors-To: icon-group-errors@cs.arizona.edu
You wrote:
>>Can anyone explain+give a usefull example of the use of <- and complex
>>backtracking in general? (Only examples in Icon will be accepted here..)
>>
Hmmm, by useful, I assume you're ruling out the 8-queens program in the
Icon book (also found in the IPL)?
I don't know if I can provide much - I think that you mean 'data backtracking'
when you say 'complex' backtracking (since that's what <- provides). Most
problems that are usefully attacked with data backtracking tend to be fairly
complex (otherwise, it's often easy to find some other approach that's not
much more difficult to use - simple problems tend to have simple solutions).
What <- gives you is the ability to 'roll-back' when backtracking decisions
that were made during the 'forward-tracking' - something that's common. It
generally takes thinking in terms of backtracking to see where it's really
useful.
Here's an example (in Icon!) of a course scheduling algorithm originally
written by Dan Higdon at the Univ. of Texas, and slightly modified by me
to handle courses at my 'old' school. As it uses recursion, control backtracking,
and data backtracking, I'd have to say it probably qualifies as 'complex', and
it's definitely been found to be useful!
(I'm also a bit reluctant to post this as an isolated piece of code - it's
part of a much larger program that allows students to experiment with
schedules, so there are parts here that take quite a bit of context...
The procedure generates successive schedules (it can indeed, produce all
possible schedules from a set of courses, if you keep resuming it...))
Anyway (warning - non-trivial code follows - on the other hand, try
coding this up in C!):
#
# The algorithm is as follows:
# If the course set is empty, return that empty set
# otherwise,
# Generate every remaining schedule and do the following with each:
# get the course name and remove it from the course set
# Generate every non-null and unconflicting time for each class, as
# well as any possible unconflicting labs for that class, then:
# insert it (and the lab) into the set
# suspend this schedule
#
procedure schedule (cs) # input is a set of desired classes
local t, schedl, class, tlab
if *cs = 0 then return cs
delete(cs,class := ?cs) # pick a desired class at random
every schedl := schedule(cs) & # first schedule all *other* classes,
# then try and fit this one (and lab)
freespace(t := !classdb[class]) & nonConflicting(t, schedl) &
(/t.lab | nonConflicting(tlab <- !\t.lab,schedl))
do { # found room, add it (and lab) to schedule
suspend set([t, \tlab] | [t])\1 ++ schedl
}
end
Control backtracking is used to 'go back and try another one' if either:
(1) there is no room in that particular class
(2) that class conflicts with already scheduled classes
(3) that course has a required lab that can't fit into the schedule
The use here of data backtracking, in:
tlab <- !\t.lab
is to restore the initial value of tlab (&null, since it's a local variable)
if none of the available labs for this course can be fit into the schedule.
freespace() checks a class to see if there are any available seats left,
with !classdb[class] producing all sections of that class...
nonConflicting() checks to be sure the section doesn't overlap with an already
scheduled class.
The /t.lab | nonConflicting(...) avoids calling nonConflicting is there is
no lab for that course, without failing.
The
set([t, \tlab] | [t])\1 ++ schedl
adds either a pair (if there was a lab), or a single (if not) to the
schedule. The limitation prevents backtracking from generating
both!
--
Steve Wampler
swampler@gemini.edu
Gemini Project (under AURA)